import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode {
}

//leetcode:53:优美的序列
class Solution1 {
    int ret = 0;
    boolean[] check;
    public int countArrangement(int n) {
        check = new boolean[n+1];
        dfs(n,1);
        return ret;
    }
    public void dfs(int n,int pos){
        if(pos == n+1){
            ret++;
            return;
        }
        for(int i = 1; i <= n;i++){
            if(check[i] == false && (i % pos == 0 || pos % i == 0)){
                //剪枝
                check[i] = true;
                dfs(n,pos+1);
                //回溯
                check[i] = false;
            }
        }
    }
}

//leetcode：51：N皇后
class Solution2 {
    List<List<String>> ret;
    List<String> path;
    boolean[] checkCol,checkDig1,checkDig2;//列，主对角线，副对角线
    public List<List<String>> solveNQueens(int n) {
        checkCol = new boolean[n];
        checkDig1 = new boolean[n*2];
        checkDig2 = new boolean[n*2];
        ret = new ArrayList<>();
        path = new ArrayList<>();
        char[][] arr = new char[n][n];
        for(int i = 0; i < n ;i++){
            Arrays.fill(arr[i],'.');//将全部格子都放成'.'
        }
        dfs(n,arr,0);
        return ret;
    }
    public void dfs(int n, char[][] arr,int row){
        if(row == n){
            path = new ArrayList<>();
            for(int i = 0; i < n;i++){
                //将一行字符串放入
                path.add(new String(arr[i]));
            }
            //将整个放入
            ret.add(new ArrayList<>(path));
        }
        for(int col = 0;col < n; col++){
            //如果列，主对角线，副对角线可以放入就将他改为'Q'
            if(checkCol[col] == false && checkDig1[row-col+n] == false && checkDig2[row+col] == false){
                arr[row][col] = 'Q';
                //存入后将对应的列，主对角线，副对角线设置为true
                checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = true;
                dfs(n,arr,row+1);
                //回溯
                arr[row][col] = '.';
                checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = false;
            }
        }
    }
}